package ch2.part1;

/**
 * 自定义的数组结构，包含插入、删除、扩容、查找、更新、输出等方法及场景
 * 时间复杂度：
 * - 插入 O(n)
 * - 删除 O(n)
 * - 扩容 O(n)
 * - 查询 O(1)
 * - 更新 O(1)
 * - 遍历 O(n)
 *
 * @author liuwanxiang
 * @version 2019/05/13
 */
public class MyArray {

    private Integer[] array;
    private Integer size;

    public MyArray(int capacity) {
        this.array = new Integer[capacity];
        this.size = 0;
    }

    /**
     * 往指定位置插入元素
     * 时间复杂度: O(n)=n
     *
     * @param index
     * @param element
     */
    public void insert(int index, Integer element) {
        // 判断下标位置，防止数组越界
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("数组越界~");
        }
        // 容量不够，数组扩容
        if (size >= array.length) {
            resize();
        }
        // 自index位置起，所有数据向后移动一位
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = element;
        size++;
    }

    /**
     * 删除指定位置的元素
     * 时间复杂度: O(n)=n
     *
     * @param index
     */
    public void delete(int index) {
        // 判断下标位置，防止数组越界
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组越界~");
        }
        // 所有位置向前移动一位，size减一
        for (int i = index; i < size; i++) {
            array[i] = array[i + 1];
        }
        size--;
    }

    /**
     * 数组扩容一倍，并将原有数据复制到新数组中
     * 时间复杂度: O(n)=n
     */
    private void resize() {
        Integer[] temp = new Integer[array.length << 1];
        System.arraycopy(array, 0, temp, 0, array.length);
        array = temp;
    }

    /**
     * 数组指定位置下标更新，并返回old值
     * 时间复杂度: O(n)=1
     *
     * @param index
     * @param element
     * @return
     */
    private Integer update(int index, Integer element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组越界~");
        }
        Integer oldVal = array[index];
        array[index] = element;
        return oldVal;
    }

    /**
     * 获取数组中指定下标元素
     * 时间复杂度: O(n)=1
     *
     * @param index
     * @return
     */
    private Integer get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组越界~");
        }
        return array[index];
    }

    /**
     * 遍历打印数组元素
     * 时间复杂度: O(n)=n
     */
    private void output() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i]);
            System.out.print(" ");
        }
        System.out.print("\n");
    }

    public static void main(String[] args) {

        MyArray myArray = new MyArray(4);
        // 3
        myArray.insert(0, 3);
        // 3 7
        myArray.insert(1, 7);
        // 3 7 9
        myArray.insert(2, 9);
        // 3 7 9 5
        myArray.insert(3, 5);
        // 3 6 7 9 5
        myArray.insert(1, 6);
        // 3 6 7 9 5 8
        myArray.insert(5, 8);
        // 3 6 0 9 5 8
        System.out.println(myArray.update(2, 0));
        // 3 6 0 5 8
        myArray.delete(3);
        // 3 6 0 5 8
        myArray.output();
        // 0
        System.out.println(myArray.get(2));

    }

}
